A
弱智题,暴力枚举即可。
Code
#include <cstdio>
int a[4], row[2], col[2], dia[2], vis[9], flag;
int main() {
scanf("%d%d%d%d%d%d", &row[0], &row[1], &col[0], &col[1], &dia[0], &dia[1]);
for (a[0] = 1; a[0] <= 9; a[0]++) {
for (a[1] = 1; a[1] <= 9; a[1]++)
for (a[2] = 1; a[2] <= 9; a[2]++)
for (a[3] = 1; a[3] <= 9; a[3]++)
if (a[0] + a[1] == row[0] && a[2] + a[3] == row[1]
&& a[0] + a[2] == col[0] && a[1] + a[3] == col[1]
&& a[0] + a[3] == dia[0] && a[1] + a[2] == dia[1]
&& a[0] != a[1] && a[1] != a[2] && a[2] != a[3]
&& a[0] != a[3] && a[0] != a[2] && a[1] != a[3]) {
printf("%d %d\n%d %d", a[0], a[1], a[2], a[3]);
return 0;
}
}
puts("-1");
return 0;
}
B
弱智字符串模拟,时间复杂度 。
Code
#include <iostream>
#include <string>
#include <cstdio>
using namespace std;
int main() {
string s; cin >> s;
if (s[0] == '-') putchar('(');
putchar(""); // 不知道为什么美元符号放在这里会渲染失败,注意这里输出美元符号。
int pos = -1;
for (int i = 0; i < s.size(); i++) if (s[i] == '.') { pos = i; break; }
if (pos == -1) {
for (int i = 0 + (s[0] == '-'); i < s.size(); i++) {
putchar(s[i]);
if ((s.size() - i - 1) % 3 == 0 && i != s.size() - 1) putchar(',');
}
printf(".00");
} else {
for (int i = 0 + (s[0] == '-'); i < pos; i++) {
putchar(s[i]);
if ((pos - i - 1) % 3 == 0 && i != pos - 1) putchar(',');
}
putchar('.');
putchar(isdigit(s[pos + 1]) ? s[pos + 1] : '0');
putchar(isdigit(s[pos + 2]) ? s[pos + 2] : '0');
}
if (s[0] == '-') putchar(')');
return 0;
}
C
考虑枚举 的约数,得到 ,更新答案即可。
时间复杂度 。
Code
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
#define int long long
vector<int> p;
inline void factor(int x) {
for (int i = 1; i * i <= x; i++) {
if (x % i == 0) {
p.push_back(i);
if (i * i != x) p.push_back(x / i);
}
}
}
int mn = 0x7fffffffffffffff, mx = -0x7fffffffffffffff;
signed main() {
int n; scanf("%lld", &n);
factor(n);
for (int i = 0; i < p.size(); i++) {
for (int j = 0; j < p.size(); j++) {
int a = p[i], b = p[j];
if (n % (a * b)) continue;
int c = n / a / b;
mn = min(min(mn, (a + 1) * (b + 2) * (c + 2)),
min((a + 2) * (b + 1) * (c + 2),
(a + 2) * (b + 2) * (c + 1)));
mx = max(max(mx, (a + 1) * (b + 2) * (c + 2)),
max((a + 2) * (b + 1) * (c + 2),
(a + 2) * (b + 2) * (c + 1)));
}
}
printf("%lld %lld\n", mn - n, mx - n);
return 0;
}
D
计数题,但是需要考虑一些细节。
当 或 时,全都填上就可以。
当 时,我们把棋盘划分成若干个田字格,每两个田字格中一个放满一个放空,最后不足一个田字格的全部填满。容易证明这是最多的方案。
其余情况直接黑白染色即可,易知最多能放 。
Code
#include <cstdio>
#include <cstdlib>
int max(int a, int b) { return a > b ? a : b; }
int min(int a, int b) { return a < b ? a : b; }
int main() {
int n, m; scanf("%d%d", &n, &m);
if (min(n, m) == 1) printf("%d\n", max(n, m));
else if (min(n, m) == 2) {
if (max(n, m) % 4 <= 2) printf("%d\n", max(n, m) / 4 * 4 + max(n, m) % 4 * 2);
else printf("%d\n", (max(n, m) / 4 + 1) * 4);
}
else printf("%d\n", (n * m + 1) / 2);
return 0;
}
E
典中典T形骨牌覆盖问题,记忆化爆搜即可。
时间复杂度不会算。
Code
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, ans, d[15][15];
char a[15][15], b[15][15];
void dfs(int x, int y, int s) {
if (x == n) {
if (s >= ans) {
ans = s;
memcpy(b, a, sizeof(b));
}
return;
}
if (a[x - 1][y - 1] == '.' &&
a[x - 1][y] == '.' &&
a[x - 1][y + 1] == '.' &&
a[x + 1][y] == '.' &&
a[x][y] == '.') {
a[x - 1][y - 1] = a[x - 1][y] = a[x - 1][y + 1] = a[x + 1][y] = a[x][y] = 'A' + s;
if (s + 1 >= d[x][y]) {
d[x][y] = max(d[x][y], s);
if (y == m - 1) dfs(x + 1, 2, s + 1);
else dfs(x, y + 1, s + 1);
}
a[x - 1][y - 1] = a[x - 1][y] = a[x - 1][y + 1] = a[x + 1][y] = a[x][y] = '.';
}
if (a[x + 1][y - 1] == '.' &&
a[x + 1][y] == '.' &&
a[x + 1][y + 1] == '.' &&
a[x - 1][y] == '.' &&
a[x][y] == '.') {
a[x + 1][y - 1] = a[x + 1][y] = a[x + 1][y + 1] = a[x - 1][y] = a[x][y] = 'A' + s;
if (s + 1 >= d[x][y]) {
d[x][y] = max(d[x][y], s);
if (y == m - 1) dfs(x + 1, 2, s + 1);
else dfs(x, y + 1, s + 1);
}
a[x + 1][y - 1] = a[x + 1][y] = a[x + 1][y + 1] = a[x - 1][y] = a[x][y] = '.';
}
if (a[x - 1][y - 1] == '.' &&
a[x][y - 1] == '.' &&
a[x][y + 1] == '.' &&
a[x + 1][y - 1] == '.' &&
a[x][y] == '.') {
a[x - 1][y - 1] = a[x][y - 1] = a[x][y + 1] = a[x + 1][y - 1] = a[x][y] = 'A' + s;
if (s + 1 >= d[x][y]) {
d[x][y] = max(d[x][y], s);
if (y == m - 1) dfs(x + 1, 2, s + 1);
else dfs(x, y + 1, s + 1);
}
a[x - 1][y - 1] = a[x][y - 1] = a[x][y + 1] = a[x + 1][y - 1] = a[x][y] = '.';
}
if (a[x - 1][y + 1] == '.' &&
a[x][y - 1] == '.' &&
a[x][y + 1] == '.' &&
a[x + 1][y + 1] == '.' &&
a[x][y] == '.') {
a[x - 1][y + 1] = a[x][y - 1] = a[x][y + 1] = a[x + 1][y + 1] = a[x][y] = 'A' + s;
if (s + 1 >= d[x][y]) {
if (y == m - 1) dfs(x + 1, 2, s + 1);
else dfs(x, y + 1, s + 1);
d[x][y] = max(d[x][y], s);
}
a[x - 1][y + 1] = a[x][y - 1] = a[x][y + 1] = a[x + 1][y + 1] = a[x][y] = '.';
}
if (y == m - 1) dfs(x + 1, 2, s);
else dfs(x, y + 1, s);
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
a[i][j] = '.';
}
if (n < 3 || m < 3) {
puts("0");
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
putchar(a[i][j]);
puts("");
}
return 0;
}
dfs(2, 2, 0);
printf("%d\n", ans);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
putchar(b[i][j]);
puts("");
}
return 0;
}